/*
巧妙背包
*/
#include<bits/stdc++.h>
using namespace std;
int f[25555],a[25555];
int main(){
    int t,n,ans;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+1+n);
        f[0]=1;
        ans=0;
        for(int i=1;i<=n;i++){
            int pd=0;
            for(int j=a[i];j<=a[n];j++)
                if(f[j]==0&&f[j-a[i]])f[j]=1,pd=1;
            if(pd)ans++;
        }
        printf("%d\n",ans);
        memset(f,0,4*(a[n]+1));
    }
}